package com.chj.leetcode.tijie450to500;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Code460_LFUCache {
	class LFUCache {
		Map<Integer, Node> cache; // 存储缓存的内容
		Map<Integer, Deque<Node>> freqMap; // 存储每个频次对应的双向链表
		int size;
		int capacity;
		int min; // 存储当前最小频次

		public LFUCache(int capacity) {
			cache = new HashMap<>(capacity);
			freqMap = new HashMap<>();
			this.capacity = capacity;
		}

		public int get(int key) {
			Node node = cache.get(key);
			if (node == null) {
				return -1;
			}
			freqInc(node);
			return node.value;
		}

		public void put(int key, int value) {
			if (capacity == 0) {
				return;
			}
			Node node = cache.get(key);
			if (node != null) {
				node.value = value;
				freqInc(node);
			} else {
				if (size == capacity) {
					Node deadNode = removeNode();
					cache.remove(deadNode.key);
					size--;
				}
				Node newNode = new Node(key, value);
				cache.put(key, newNode);
				addNode(newNode);
				size++;
			}
		}

		void freqInc(Node node) {
			// 从原freq对应的链表里移除, 并更新min
			int freq = node.freq;
			Deque<Node> queu = freqMap.get(freq);
			queu.remove(node);
			if (freq == min && queu.size() == 0) {
				min = freq + 1;
			}
			// 加入新freq对应的链表
			node.freq++;
			Deque<Node> newSet = freqMap.get(freq + 1);
			if (newSet == null) {
				newSet = new ArrayDeque<>();
				freqMap.put(freq + 1, newSet);
			}
			newSet.add(node);
		}

		void addNode(Node node) {
			Deque<Node> queu = freqMap.get(1);
			if (queu == null) {
				queu = new ArrayDeque<>();
				freqMap.put(1, queu);
			}
			queu.add(node);
			min = 1;
		}

		Node removeNode() {
			Deque<Node> set = freqMap.get(min);
			Node deadNode = set.iterator().next();
			set.remove(deadNode);
			return deadNode;
		}
	}

	class Node {
		int key;
		int value;
		int freq = 1;

		public Node(int key, int value) {
			this.key = key;
			this.value = value;
		}
	}

//
//	作者：sweetiee
//	链接：https://leetcode-cn.com/problems/lfu-cache/solution/java-13ms-shuang-100-shuang-xiang-lian-biao-duo-ji/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
